This invention relates in general to the field of computers, and in particular to image retrieval from large image databases, such as photographic archives, digital libraries, catalogs, and videos.
Various techniques are commonly employed for retrieving images stored in a database. The most conventional technique for storing and retrieving images that match a desired characteristic is to associate key words with each image, such as xe2x80x9cportraitxe2x80x9d, xe2x80x9cseascapexe2x80x9d, xe2x80x9cmountainxe2x80x9d, xe2x80x9cpresidentsxe2x80x9d, etc. Having associated such key words to the images, a user provides one or more search words to the search or retrieval system, and the system presents one or more images in dependence upon the degree of correspondence between the search words and stored key words. Conventional Internet search engines are examples of such text based retrieval means.
Text based image retrieval, however, requires the categorizing of each picture by keywords, which can be a burdensome process if applied to hundreds or thousands of images; also, the individual choice of keywords limits the effectiveness of the search to the degree of correspondence between the words the categorizer used se describe the stored images, and the words the searcher uses to describe the desired image.
Graphics based retrieval is a more intuitive approach to image retrieval. Conventional graphic based retrieval systems employ various forms of color or pattern matching. A graphics based system, however, can be computationally intensive. Computer images are typically stored as an array of thousands of pixels, and the color of each of the thousands of pixels is encoded as a 24-bit red-green-blue (RGB) value. The comparison of a target image to a collection of reference images based on these thousands of 24-bit values is computationally impractical, and a pixel-by-pixel comparison may not provide a measure of similarity that correlates to the human visual system. Practical graphics based systems, therefore, characterize an image based on an abstraction of the image, and the comparisons among images are based on the abstractions. The conventional abstractions include a partitioning of the image into an array of partitions, wherein the number of partitions is substantially less than the number of pixels in the image. Comparisons among images are based on a comparison of each corresponding partition in the images, rather than a comparison of each corresponding pixel in the images.
The conventional abstractions also include a quantization of the color value into a smaller, less precise, color value. For example, a 24-bit RGB value may be quantized to one of 64 common colors, for example, the 64 colors that might be contained in a box of 64 crayons. Such an abstraction retains the substantial color qualities of the image, but uses only 6-bits per pixel, rather than 24. Using this quantization, the characteristics of a partition of an image is encoded as a histogram of the number of occurrences of pixels of each quantized color value within the partition.
A comparison of the histograms representing the colors in each partition in the images can provide for a measure of similarity between images. Histograms are, however, by their very nature, multidimensional. A comparison between two histograms is multidimensional and does not directly provide for a single valued measure of similarity. Conventional statistical methods of comparing the number of occurrences of events, based, for example on a chi-square test, can be used to compare histograms. Conventional methods used to compare histograms, however, do not take into account the sensitivities of the human perception system. For example, of the 64 quantized colors discussed above, multiple shades of green may be provided, including xe2x80x9civyxe2x80x9d and xe2x80x9cemeraldxe2x80x9d. One image may contain a substantial number of occurrences of the quantized xe2x80x9civyxe2x80x9d color, whereas another image may contain a substantial number of occurrences of the quantized xe2x80x9cemeraldxe2x80x9d color. A conventional histogram comparator would not necessarily determine a similarity between these images, because they contain xe2x80x9cdifferentxe2x80x9d colors. Reducing the number of quantization levels, for example to the six primary colors plus black and white, eliminates this problem by quantizing all shades of green to the same xe2x80x9cgreenxe2x80x9d value. Such a reduction, however, will preclude an ability to identify a stronger similarity between images that do, in fact, have corresponding shades of color, such as xe2x80x9civyxe2x80x9d or xe2x80x9cemeraldxe2x80x9d.
The conventional method of quantizing colors also uses an a priori determination of the quantization levels. Choosing the 64 colors of a common box of crayons may provide for an effective quantization scheme for images in general, but it may not be suitable for all database collections. For example, if the image database is a database of portraits, having multiple shades of green or violet colors would not provide the same distinguishing capabilities as having varying shades of hair and flesh colors.
Therefore, a need exists for a method and apparatus that provides a similarity measure between images that is based on the human perceptive system. A need also exists for a method and apparatus that provides for a comparison between images that is based on the expected color content of the images.